package LeetCode;

import java.util.*;

public class Code207_canFinish {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites == null || prerequisites.length == 0){
            return true;
        }
        Map<Integer, HashSet<Integer>> map = new HashMap<>();
        for (int i = 0; i < prerequisites.length; i++) {
            if (!map.containsKey(prerequisites[i][0])){
                map.put(prerequisites[i][0], new HashSet<>());
            }
            if (!map.containsKey(prerequisites[i][1])){
                map.put(prerequisites[i][1], new HashSet<>());
            }
            map.get(prerequisites[i][0]).add(prerequisites[i][1]);
        }
        int num = 0;
        Queue<Integer> queue = new LinkedList<>();
        while (num < map.size()){
            for (Integer key : map.keySet()){
                if (map.get(key).size() == 0){
                    queue.offer(key);
                    map.get(key).add(Integer.MIN_VALUE);
                    num++;
                }
            }
            if (queue.isEmpty()){
                return false;
            }
            while (!queue.isEmpty()){
                Integer temp = queue.poll();
                for (Integer key : map.keySet()){
                    map.get(key).remove(temp);
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] prerequisites = new int[][]{
                {1,0},{2,6},{1,7},{5,1},{6,4},{7,0},{0,5}};
        int numCourses = 8;
        Code207_canFinish code207_canFinish = new Code207_canFinish();
        System.out.println(code207_canFinish.canFinish(numCourses, prerequisites));
    }
}
